2023 SEECTF

Van1sh 比赛小屋 Write Up
创建时间:
字数:8.9k 阅读:
  1. 入门难度
    1. BabyRC4
      1. exploit
    2. Dumb Chall
      1. exploit
    3. OpenEndedRSA
      1. exploit
  2. 初级难度
    1. Qskates
      1. exploit
  3. 中级难度
    1. Semaphore
      1. exploit
  4. 高级难度
    1. onelinecrypto
    2. Romeo and Juliet
    3. Isogeny Maze
    4. Shard

long time no see，于是打（复现）了 seectf，然后被虐惨了，题目都没有做完，因为已经不配做后面的题目了。总共有 12 道密码学分类的题目，涉及的面很广，题目的质量也很高，有难有易，能学到新姿势与新知识。体验非常不错！ 其实已经被击碎了。

至于赛题，咱们从易到难，慢慢感受好了。

入门难度

BabyRC4

Warri
157 solves / 262 points
I have a simple RC4 encryption oracle. Shouldn’t be that hard to break…right?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Cipher import ARC4
from os import urandom
key = urandom(16)
flag = b'SEE{?????????????????????????????????}'[::-1]

def enc(ptxt):
    cipher = ARC4.new(key)
    return cipher.encrypt(ptxt)

print(f"c0 = bytes.fromhex('{enc(flag).hex()}')")
print(f"c1 = bytes.fromhex('{enc(b'a'*36).hex()}')")

"""
c0 = bytes.fromhex('b99665ef4329b168cc1d672dd51081b719e640286e1b0fb124403cb59ddb3cc74bda4fd85dfc')
c1 = bytes.fromhex('a5c237b6102db668ce467579c702d5af4bec7e7d4c0831e3707438a6a3c818d019d555fc')
"""

可以看到第一个题目还是非常简单，针对流密码的已知明文攻击，题目首先将 flag 加密并给出了密文，随后又加密了 b'a'*36，但是注意到两次加密都是调用了 enc 函数，而每次调用enc函数都会重新用 key 初始化一个 ARC4 对象，因此两次加密所使用密钥流其实是一致的，因此只需要异或 b'a'*36 和对应的密文得到密钥流，再异或 flag 的密文就能解密获得对应 flag 了。不过由于 flag 是 38 个字节，我们还有 2 个字节不能恢复。不过注意到 flag 的格式是 SEECTF，并且加密的时候也是翻转了的，因此不能恢复的两个字节就是 SE

exploit

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.strxor import strxor

m1 = b'a'*36
c0 = bytes.fromhex('b99665ef4329b168cc1d672dd51081b719e640286e1b0fb124403cb59ddb3cc74bda4fd85dfc')
c1 = bytes.fromhex('a5c237b6102db668ce467579c702d5af4bec7e7d4c0831e3707438a6a3c818d019d555fc')

flag = strxor(c0[:-2],strxor(m1,c1))
flag = b"SE"+flag[::-1]
print(flag)

# b'SEE{n3vEr_reU53_rC4_k3y5ss5s:cafe2835}'

Dumb Chall

TheMythologist
85 solves / 388 points
This sus pigeon wants to prove that an object is ultraviolet in colour, but I’m ultraviolet-blind!

nc win.the.seetf.sg 3002

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import random
import time
from Crypto.Util.number import bytes_to_long, isPrime

#from secret import FLAG
FLAG = "VCTF{so_easy}"

def fail():
    print("You have disappointed the pigeon.")
    exit(-1)


def generate_prime_number(bits: int = 128) -> int:
    num = random.getrandbits(bits)
    while not isPrime(num):
        num += 1
    return num


def generate_random_boolean() -> bool:
    return bool(random.getrandbits(1))


def first_verify(g, p, y, C, w, r) -> bool:
    assert w
    return ((y * C) % p) == pow(g, w, p)


def second_verify(g, p, y, C, w, r) -> bool:
    assert r
    return pow(g, r, p) == C


p = generate_prime_number()
g = random.getrandbits(128)
x = bytes_to_long(FLAG.encode())
y = pow(g, x, p)

print(f"p = {p}")
print(f"g = {g}")
print(f"y = {y}")

print("Something something zero-knowledge proofs blah blah...")
print("Why not just issue the challenge and the verification at the same time? Saves TCP overhead!")

seen_c = set()
for round in range(30):
    w, r = None, None
    choice = generate_random_boolean()
    if not choice:
        w = int(input("Enter w: "))
        C = int(input("Enter C: "))
        if C in seen_c:
            fail()
        seen_c.add(C)
        verify = first_verify
    else:
        r = int(input("Enter r: "))
        C = int(input("Enter C: "))
        if C in seen_c:
            fail()
        seen_c.add(C)
        verify = second_verify
    if not verify(g, p, y, C, w, r):
        fail()
    else:
        print(f"You passed round {round + 1}.")
time.sleep(1)
print(
    "You were more likely to get hit by lightning than proof correctly 30 times in a row, you must know the secret right?"
)
print(f"A flag for your troubles - {FLAG}")

已知信息，$p,g,y$，其中 $y \equiv g^x \pmod p$。

  1. 想要获得 FLAG 需要过 30 个round，每一个round有两种可能：
  2. first_verify： 满足式子 $y \cdot C \equiv g^w \pmod p$ ，其中 $w$ 和 $C$ 可控；
  3. second_verify：满足式子 $g^r \equiv C \pmod p$，其中 $r$ 和 $C$ 可控。
  4. 另外要求每次传入的 $C$ 都不同。

对于 second_verify，由于 $r,C$ 可控，所以在本地随便选一个 $r$，再算出对应的 $C$ 即可。

对于 first_verify，$y\cdot C \equiv g^w \to g^x \cdot g^r \equiv g^w$，因此我们需要控制 $w = x \cdot r$，由于我们不知道 $x$ 的值似乎我们无法通过验证。

但是我们知道 $y \equiv g^x \pmod p$，因此我们可以给出 $C’ \equiv y^{-1} \equiv g^{-x} \pmod p$，这样就能有 $y \cdot C’ \equiv g^x \cdot g^{-x} \equiv g^0 \pmod p$，于是 $w = 0$。至于每次需要 $C$ 不同，我们可以构造 $C’_i \equiv \ C’\cdot g^i$，对应的设置 $w = i$。

exploit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from pwn import *
from Crypto.Util.number import *
#sh = process(["python3","main.py"])
sh = remote("win.the.seetf.sg",3002)
sh.recvuntil("p = ")
p = int(sh.recvuntil("\n")[:-1])
sh.recvuntil("g = ")
g = int(sh.recvuntil("\n")[:-1])
sh.recvuntil("y = ")
y = int(sh.recvuntil("\n")[:-1])

for i in range(1,31):
	choices = sh.recvuntil(": ")
	if b"Enter w" in choices:
		print("w")
		C = inverse(y,p)*pow(g,i,p)
		w = i
		sh.sendline(str(w))
		sh.recvuntil(": ")
		sh.sendline(str(C))
	elif b"Enter r" in choices:
		print("r")
		r = i
		C = pow(g,r,p)
		sh.sendline(str(r))
		sh.recvuntil(": ")
		sh.sendline(str(C))

sh.interactive()

OpenEndedRSA

Warri
74 solves / 406 points
I was told my RSA implementation is extremely insecure and vulnerable… I’ll make this open ended for yall to take a look…find the vulnerability and I’ll give you the flag!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Util.number import *
from gmpy2 import iroot # this helps with super accurate square root calculations!

flag = b'????????????????????????'
m = bytes_to_long(flag)
e = 0x10001
pp = bytes_to_long(b'????????????????')
s = 1
assert isPrime(pp)

while not isPrime(s):
    p = getPrime(512)
    s = p**2 + pp**2 

assert iroot(s-pp**2,2) == (p, True)  # quick demo on how to use iroot()
assert s%2 == 1                       # duh, s is a prime number after all!

q = getPrime(512)
n = p*q
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
print(f's = {s}')

"""
n = 102273879596517810990377282423472726027460443064683939304011542123196710774901060989067270532492298567093229128321692329740628450490799826352111218401958040398966213264648582167008910307308861267119229380385416523073063233676439205431787341959762456158735901628476769492808819670332459690695414384805355960329
e = 65537
c = 51295852362773645802164495088356504014656085673555383524516532497310520206771348899894261255951572784181072534252355368923583221684536838148556235818725495078521334113983852688551123368250626610738927980373728679163439512668552165205712876265795806444660262239275273091657848381708848495732343517789776957423
s = 128507372710876266809116441521071993373501360950301439928940005102517141449185048274058750442578112761334152960722557830781512085114879670147631965370048855192288440768620271468214898335819263102540763641617908275932788291551543955368740728922769245855304034817063220790250913667769787523374734049532482184053
"""

一个 RSA 的题目，额外给出了参数 $s$，其中 $s = p^2 + pp^2$，并且满足 $s,p,pp$ 都是素数，那么根据奇偶性就能判断 $pp$ 是一个偶素数，也就是 $2$，于是我们就能直接算出 $p$，继而解密 RSA 了。

exploit

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import *
from gmpy2 import *
n = 102273879596517810990377282423472726027460443064683939304011542123196710774901060989067270532492298567093229128321692329740628450490799826352111218401958040398966213264648582167008910307308861267119229380385416523073063233676439205431787341959762456158735901628476769492808819670332459690695414384805355960329
e = 65537
c = 51295852362773645802164495088356504014656085673555383524516532497310520206771348899894261255951572784181072534252355368923583221684536838148556235818725495078521334113983852688551123368250626610738927980373728679163439512668552165205712876265795806444660262239275273091657848381708848495732343517789776957423
s = 128507372710876266809116441521071993373501360950301439928940005102517141449185048274058750442578112761334152960722557830781512085114879670147631965370048855192288440768620271468214898335819263102540763641617908275932788291551543955368740728922769245855304034817063220790250913667769787523374734049532482184053
p = iroot(s - 4,2)[0]
q = n//p
m = pow(c,inverse(e,(p-1)*(q-1)),n)
print(long_to_bytes(m))

# b'SEE{0dd_3vEN:deadbeef}'

初级难度

Qskates

Warri
9 solves / 491 points
Alice and Bob love skating so much, they’ve gotten Eve into it!

Turns out Eve is a skater herself and wants to know Alice’s secret. She’s placed herself right in the middle of their conversation, can you help her figure out the secret?

nc win.the.seetf.sg 3004

对这一题的定位其实是不那么准确的，因为从解题上来说，其实操作起来是比较简单的，但是如果要去深究其背后的原理，又会比较复杂，可能这也是解题人数比较少的原因叭，量子电路的框架可能让很多人望而却步了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#!/usr/bin/env python3

from qiskit import QuantumCircuit, Aer
from numpy.random import randint
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
import hashlib

def encode_message(bits, bases):
	message = []
	for i in range(n):
		qc = QuantumCircuit(1,1)
		if bases[i] == 0: 
			if bits[i] == 0:
				pass 
			else:
				qc.x(0)
		else:
			if bits[i] == 0:
				qc.h(0)
			else:
				qc.x(0)
				qc.h(0)
		qc.barrier()
		message.append(qc)
	return message

def measure_message(message, bases):
	measurements = []
	for q in range(min(n,len(bases))):
		if bases[q] == 0: 
			message[q].measure(0,0)
		if bases[q] == 1: 
			message[q].h(0)
			message[q].measure(0,0)
		aer_sim = Aer.get_backend('aer_simulator')
		result = aer_sim.run(message[q], shots=1, memory=True).result()
		measured_bit = int(result.get_memory()[0])
		measurements.append(measured_bit)
	return measurements

def remove_garbage(a_bases, b_bases, bits):
	good_bits = []
	for q in range(n):
		if a_bases[q] == b_bases[q]:
			good_bits.append(bits[q])
	return good_bits

def verifyInput(lst):
	for i in lst:
		if i != 0 and i != 1:
			return False
	return True

n = 100

alice_bits = randint(2,size=n)
alice_bases = randint(2, size=n)
bob_bases = randint(2, size=n)


message = encode_message(alice_bits, alice_bases)
bob_results = measure_message(message, bob_bases)
alice_key = remove_garbage(alice_bases, bob_bases, alice_bits)
bob_key = remove_garbage(alice_bases, bob_bases, bob_results)
assert alice_key == bob_key





flag = b"VCTF"*4#pad(open('flag.txt','rb').read(),16)
key = hashlib.sha256(''.join([str(i) for i in alice_key]).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
enc = cipher.encrypt(flag)
print(f'iv = {iv.hex()}')
print(f'enc = {enc.hex()}')

while True:
	message = encode_message(alice_bits, alice_bases)
	
	eve_bases = [int(i) for i in input("Enter bases to intercept: ")]
	assert verifyInput(eve_bases)

	eve_results = measure_message(message, eve_bases)
	print("Measured message:", eve_results)
	
	new_bits = [int(i) for i in input("Enter bits to send to Bob: ")]
	assert verifyInput(new_bits)
	new_bits += alice_bits.tolist()[len(new_bits):]
	
	new_message = encode_message(new_bits, alice_bases)
	bob_results = measure_message(new_message, bob_bases)
	
	alice_key = remove_garbage(alice_bases, bob_bases, alice_bits)
	bob_key = remove_garbage(alice_bases, bob_bases, bob_results)
	print(alice_key == bob_key)

由于我也不具有任何量子电路相关的知识储备，因此这一题我们直接抛开它不谈，直接把他当作一个黑盒进行测试即可（其实如果在比赛中遇见陌生的密码学体制，或者算法，我们无法在短时间内去理解的话，这也是一种解题的方式）

先忽略代码中所以的函数定义部分，我们先初步了解整个流程

  1. alice 会生成自己的 bits 和 bases

  2. bob 会有自己的 bases

  3. alice 和 bob 进行密钥协商，第一步是 alice 将 bits 和 bases 结合通过 encode_message 函数处理后得到 message 给到 bob

  4. bob 将 message 和 bob_bases 通过 measure_message 函数处理后得到 bob_results

  5. alice_key 和 bob_key 可以通过 remove_garbage 函数获得，这个函数我们需要去阅读一下。基于 alice 和 bob 的 bases ，如果他们两个的 bases 某处的bit 相同，就获取 alice_bits 和 bob_results对应位置的比特作为密钥。

于是我们得到结论：alice_bits 和 bob_results 的地位是相等的。由于满足 assert alice_key == bob_key，因此当 alice_bases 和 bob_bases 的比特相同时，对应位置的 alice_bits 和 bob_results 的也相同。

举例：

1
2
3
4
5
Alice bits: 001000110
Alice base: 010010001
Bob   baes: 001000100
Bob result: 0??0?0?1?
alice key = bob key: 0001

根据题目的要求，我们需要获取 alice key(bob key) 来作为 AES 的密钥对密文进行解密，而题目提供一个实现中间人攻击的场景，每一次交互我们可以：

  1. 提供一个自己的 base（eve_bases），然后可以得到对应的 results
  2. 从左往右篡改 alice bits 任意字节，字节不足会用原 Alice bits 补齐。随后这个篡改后的 new_bits 会和 alice bits “结合”生成 message 传给 bob，bob 通过该 message 获取计算 bob key 并返回其是否与 alice key 相等。

那么我们考虑，

  1. 如果我们在第二步不做任何更改，输入为空，会返回 True
  2. 如果我们输入 1，而原来的 Alice bits 的第一个bit就是 1，会返回 True，
  3. 如果我们输入 1，而原来的 Alice bits 的第一个 bit 就是 0，但是 alice base 和 Bob base 的第一个 bit 不相等，因此 Alice bits 的第一个比特不影响 Alice key，会返回 True
  4. 如果我们输入 1，而原来的 Alice bits 的第一个 bit 就是 0，并且 alice base 和 Bob base 的第一个相等，因此 Alice bits 的第一个比特影响 Alice key，会返回 False。

于是我们得到结论（以第一个比特为例）：

  1. 如果输入 1 和 0 ，均返回 True：说明 Alice 和 Bob 的base 不相等，该 bit 对 key 不产生影响
  2. 如果输入 1，返回 False；输入 0 返回 True：说明 Alice bit 为 0，并且 Alice 和 Bob 的base 相等，Alice key 为 0
  3. 如果输入 0，返回 False；输入 1 返回 True：说明 Alice bit 为1，并且 Alice 和 Bob 的base 相等，Alice key 为 1

以此类推我们可以逐比特获取完整 Alice key，随后解密密文，获得flag

exploit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from pwn import *
from numpy.random import randint
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
import hashlib

#sh = process(["python3","chall.py"])
#context.log_level = 'debug'
sh = remote("win.the.seetf.sg",3004)
sh.recvuntil("iv =")
iv = bytes.fromhex(sh.recvuntil("\n")[:-1].decode())
sh.recvuntil("enc = ")
enc =  bytes.fromhex(sh.recvuntil("\n")[:-1].decode())

key = ""

sh.recvuntil("Enter bases to intercept:")
sh.sendline("0")
sharekey = ""

while len(key)<100:
	sh.recvuntil("Enter bits to send to Bob:")
	sh.sendline(key+"0")
	judge = sh.recvuntil("Enter bases to intercept:")
	
	if b"False" in judge:
		key += "1"
		sharekey += "1"
		sh.sendline("0")
	else:
		sh.sendline("0")
		sh.recvuntil("Enter bits to send to Bob:")
		sh.sendline(key+"1")
		judge = sh.recvuntil("Enter bases to intercept:")
		sh.sendline("0")
		if b"True" in judge:
			key += "0"
		else:
			key += "0"
			sharekey += "0"
	print(sharekey)


key = hashlib.sha256(''.join([str(i) for i in sharekey]).encode()).digest()[:16]
cipher = AES.new(key=key, iv=iv, mode=AES.MODE_CBC)
flag = cipher.decrypt(enc)
print(flag)

回顾一下我们在对整个题目分析时候丝毫没有提到与量子电路相关的知识，因为这一部分相关处理全部在 encode_message 和 measure_message 函数中，而我们直接把他视为黑盒，只是当作一种生成 bob_results 的方式。（除非生成 bob_results 的过程中存在漏洞点我们可以利用，不然对于解题来说其实并不需要关心其具体是如何生成的）

中级难度

Semaphore

Neobeo
17 solves / 483 points
I’m signing with my flag so you know it’s the real deal.

1
2
3
4
5
6
7
8
9
10
11
12
13
import ecdsa # https://pypi.org/project/ecdsa/
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

sk = ecdsa.SigningKey.generate()
for nibble in flag.hex():
    signature = sk.sign(flag + nibble.encode())
    print(signature.hex())

# Code ends here. The output is printed below.
'''
04a226648...

代码越短，选手越惨。

题目言简意赅，给出了多个消息 ecdsa 的签名，而消息的组成是 flag 加上一个十六进制字符。

切入点就在于此，消息可以看作是 FLAG + @，而 @ 只有十六种可能。不过由于签名中引入了临时密钥，因此每一个签名值都是不一样的。但是如果我们能够消除其中的随机性，那么十六种明文应该也只会映射出十六种结果。而由于flag 是 SEE{ } 的格式，因此我们能够获取一部分的映射关系。

看到 ECDSA 的相关原理

由于在计算签名的过程中明文都会被hash，这部分肯定是没法逆的，因此我们最多也就只能是获取到十六个哈希然后再来“猜”对应的明文。那么如何仅根据 $r,s$ 获取哈希 $z$ 呢？

光看签名的生成过程似乎没有思路，在wiki上我们发现可以根据 r,s 恢复公钥的部分内容

可以发现 $Q_A = -zr^{-1} \times G+sr^{-1}\times R$

其中 $G$ 是曲线的生成元，包括 ecdsa 用的曲线和相关参数，这部分都是默认已知的信息，我们可以通过 python 相关的库去获取这些值。

然后我们可以通过 $r$ 去计算 $R$，因此计算 $Q_A$ 我们的未知量就是 $-zG$，注意到 $zG$ 是关于消息哈希的一个点，和哈希值是一一对应的，换句话说，$zG$ 也就只有十六种可能。再根据式子来看，我们知道 $zG$ 能够计算 $Q_A$，那再换句话来说，知道 $Q_A$ 也就能够获取 $zG$ 了，于是我们的问题就到了获取 $Q_A$ 上。

既然有两个未知量，理论上解方程我们就需要两条方程，那么如何找这两条方程呢？我们知道 flag 是以 SEE{ 开头，看到其十六进制 5345457b，第 0 个和 第 3 个字节都是 5，于是我们拿到第 0 个和第 3 个签名，有式子
$$
Q_A = -zr_0^{-1} \times G+s_0r_0^{-1}\times R_0
$$

$$
Q_A = -zr_3^{-1} \times G+s_3r_3^{-1}\times R_3
$$

$$
(r_0^{-1} - r_3^{-1})zG =s_0r_0^{-1}\times R_0-s_3r_3^{-1}\times R_3
$$

$$
zG = \frac{s_0r_0^{-1}\times R_0-s_3r_3^{-1}\times R_3}{(r_0^{-1} - r_3^{-1})}
$$

恢复了 $zG$ 我们就能计算 $Q_A$，有了 $Q_A$ 我们就能计算其他的 $zG$了，不过需要注意到的是在计算 $zG$ 的过程中用到了 $R_i$，而我们仅知道 $r_i$，根据 $r_i$ 是会恢复出两个 $R_i$ 的，因此恢复出来的公钥也会有两种情况，这个我们后续还要处理一下。比如我们注意到第 5 个字节也是 ‘5’ ，也可以用来恢复公钥，然后我们就可以对”候选公钥“们取交集了。

之后恢复出所有的 $zG$ 后，我们建立其 $x$ 轴坐标与十六进制之间的映射关系，根据

b"SEE{}".hex()
1
2
>>> b"SEE{}".hex()
'5345457b7d'

我们能够得到 $5,3,4,7,b,d$ 的映射关系，剩下来还有 10 个字符，排列一下也就是 $A_{10}^{10}=10!$ 种可能。那么如何判断映射结果是否正确呢？一个指标是 flag 肯定都是可见字符，另一个决定性指标就是我们也可以计算其签名，如果和给出的签名一致说明我们恢复出了正确的flag（使用这个指标运算速度较慢，因此可以结合第一个指标，符合第一个指标的结果再用第二个指标进行判断）。

exploit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
s='''...
'''

p=6277101735386680763835789423207666416083908700390324961279
a=-3
b=2455155546008943817740293915197451784769108058161191238065
order = 6277101735386680763835789423176059013767194773182842284081
E = EllipticCurve(GF(p),[a,b])
G = E(602046282375688656758213480587526111916698976636884684818,174050332293622031404857552280219410364023488927386650641)

data = s.split("\n")
#for each in s:
each = data[0]
r0,s0 = int(each[:48],16),int(each[48:],16)
R0 = E.lift_x(Integer(r0))

each = data[2]
r2,s2 = int(each[:48],16),int(each[48:],16)
R2 = E.lift_x(Integer(r2))


each = data[3]
r3,s3 = int(each[:48],16),int(each[48:],16)
R3 = E.lift_x(Integer(r3))

each = data[4]
r4,s4 = int(each[:48],16),int(each[48:],16)
R4 = E.lift_x(Integer(r4))

each = data[5]
r5,s5 = int(each[:48],16),int(each[48:],16)
R5 = E.lift_x(Integer(r5))



zG5 = ((int(s0*pow(r0,-1,order))*R0-int(s3*pow(r3,-1,order))*R3))*int(pow(pow(r0,-1,order)-pow(r3,-1,order),-1,order))
# zG = ((int(s0*pow(r0,-1,order))*R0-int(s5*pow(r5,-1,order))*R5))*int(pow(pow(r0,-1,order)-pow(r5,-1,order),-1,order))
QA = -zG5*int(pow(r0,-1,order))+(int(s0*pow(r0,-1,order)))*R0
# QA = -zG*int(pow(r5,-1,order))+(int(s5*pow(r5,-1,order)))*R5


import hashlib 
from Crypto.Util.number import *


from itertools import permutations
from tqdm import tqdm

dic = {}
flag = ""
index = 0
table = "5347b"+"012689"+"d"+"caef"
for i in range(len(data)):
	each = data[i]
	r,s = int(each[:48],16),int(each[48:],16)
	R = E.lift_x(Integer(r))
	zG1 = int(r)*(QA - (int(s*pow(r,-1,order)))*R)
	zG2 = int(r)*(QA - (int(s*pow(r,-1,order)))*-R)
	if zG1.xy()[0] in dic:
		flag += dic[zG1.xy()[0]]
	elif zG2.xy()[0] in dic:
		flag += dic[zG2.xy()[0]]
	else:
		dic[zG1.xy()[0]] = table[index]
		dic[zG2.xy()[0]] = table[index]
		flag += table[index]
		index+=1

table = "5347b"+"012689"+"d"+"caef"

each = data[0]
r,s = int(each[:48],16),int(each[48:],16)
R = E.lift_x(Integer(r))
u2 = s * pow(r,-1,order)

from string import printable
def check(s):
	for each in s:
		if each not in "1234567890QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm{}_-!@#$":
			return False
	return True

for each in tqdm(permutations("012689caef",int(10))):
	table2 = "5347b"+"".join(i for i in each[:6])+"d"+"".join(i for i in each[6:])
	table3 = str.maketrans(table,table2)
	FLAG = flag.translate(table3)
	if not check(bytes.fromhex(FLAG).decode('latin1')):
		continue
	FLAG = bytes.fromhex(FLAG)+b"5"
	#print(FLAG)
	
	e = bytes_to_long(hashlib.sha1(FLAG).digest())
	u1 = -e * pow(r,-1,order)
	QAt1 = int(u1) * G + int(u2) * R
	QAt2 = int(u1) * G - int(u2) * R
	if QAt1.xy()[0] == QA.xy()[0] or QAt2.xy()[0] == QA.xy()[0]:
		print(FLAG)
		break

到目前为止，还都是笔者能力范围之内的题目，虽然有知识盲区（量子电路），但还能够使用做题技巧来“蒙混过关”。但接下来的题目，就直接把我击碎了，等我把自己拼起来再更。。。

接下来就是 SEECTF 不敢 SEE 的部分了。

高级难度

onelinecrypto

Neobeo
14 solves / 486 points
How to bypass this line?

1
assert __import__('re').fullmatch(r'SEE{\w{23}}',flag:=input()) and not int.from_bytes(flag.encode(),'big')%13**37

这一次的题目就更绝了，代码就一行，然而。。。

我们看到题目是要求 flag 字符串转整型后是 $13^{37}$ 的倍数，用公式表示为就是
$$
f = \sum_{i=0}^nchr(flag[i])\cdot 256^i \equiv 0 \pmod{13^{37}}
$$
其中我们知道 flag 的格式为 SEE{*****} 中间是 23 个字符，范围是大小写字母、数字 和 下划线。

可以看到这就是一个子集和问题，也就是我们比较熟悉的背包问题的一个变体，这里不再是一个 0 1 背包，而是一个 48 - 122 背包。想当然的我们构造如下格
$$
M =
\begin{bmatrix}
1&0&0&\dots&0&0&2^8 \newline
0&1&0&\dots&0&0&2^{16} \newline
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots \newline
0&0&0&\dots&1&0&2^{8\cdot i}\newline
0&0&0&\dots&0&1&C\newline
0&0&0&\dots&0&0&13^{37}\newline
\end{bmatrix}
$$
其中 C 是我们根据已知的部分得到的常数。

那么我们希望的就是存在一个由 flag 字符组成的向量 $F=(a_1,a_2,\cdots,a_i,1,-k)$，使得

$v=F\cdot M = (a_1,a_2,\cdots,a_i,1,0)$

不过由于向量 $v$ 几乎每一个元素都是大于 $48$ 的，对于格基规约算法 LLL 来说模长还是有点长了。一个很自然的优化方式就是，我们做一个类似 center_lift 的操作，即对每一个元素提前减去平均值 $85 = (48+122)/2$ ，这样 $F$ 中的每一个元素就会在区间 $[-37,37]$ 。

这里借用 maple 的代码，不得不说他这样的构造格的方式确实要优雅很多，膜！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import string
import re

chrs = (string.ascii_letters + string.digits + "_").encode()
avg = sorted(chrs)[len(chrs) // 2] - 1
print(avg)
print([x - avg for x in sorted(chrs)])  # within [-37, 37]

M = 13**37
C = int.from_bytes(b"SEE{" + b"\x00" * 23 + b"}", "big")

P = PolynomialRing(ZZ, "ap", 23)
aps = P.gens()
aa = [ap + avg for ap in aps]
f = C + sum([a * 256**i for i, a in enumerate(aa)]) * 256
print(f)

L = matrix(f.coefficients()).T
L = block_matrix([[1,L],[0,M]])
scale = [1]*24 + [2**20]
Q = diagonal_matrix(scale)
L *= Q
L = L.BKZ(block_size=25)
L /= Q


for row in L:
    if row[-2] < 0:
        row = -row
    if row[-1] == 0 and row[-2] == 1:
        print(row)
        print(f(*row[:-2]) % M == 0)
        aa = [x + avg for x in row[:-2]][::-1]
        flag = b"SEE{" + bytes(aa) + b"}"
        assert int.from_bytes(flag, "big") % M == 0
        print(flag)


# (29, -16, -4, -9, 2, 23, -33, 1, 3, 4, 20, -20, 4, 38, -4, 17, -9, 15, 12, -26, -39, -4, -25, 1, 0)
# True
# b'SEE{<Q.;adLfQ{YAiYXV4lWLQEr}'

很不幸，还是有几个不符合要求的字符，于是maple采用了一个枚举的操作，具体的原理不是很清楚，但是看结果似乎是通过”神奇”的微调，然后能够找到很多组满足要求的短向量，然后再从中找到符合题目要求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from fpylll import IntegerMatrix, LLL
from fpylll.fplll.gso import MatGSO
from fpylll.fplll.enumeration import Enumeration

sols = []

L[:, -1] *= 2**10

A = IntegerMatrix.from_matrix(L.change_ring(ZZ))
LLL.reduction(A)
MG = MatGSO(A)
MG.update_gso()
sol_cnt = 10000
enum = Enumeration(MG, sol_cnt)
size = int(L.nrows())
bound = 37
answers = enum.enumerate(0, size, (size * bound**2), 0, pruning=None)
for _, s in answers:
    v = IntegerMatrix.from_iterable(1, A.nrows, map(int, s))
    sv = v * A

    if  sv[0, -2] in (-1, 1) and sv[0,-1] == 0:
        neg = sv[0, -2]
        sol = [neg * sv[0, i] for i in range(23)]
        assert f(*sol) % M == 0
        aa = [x + avg for x in sol][::-1]
        flag = b"SEE{" + bytes(aa) + b"}"
        assert int.from_bytes(flag, "big") % M == 0
        print(flag)
        try:
            if re.fullmatch(r"SEE{\w{23}}", flag.decode()):
                print("FOUND")
                break
        except UnicodeDecodeError:
            pass
# SEE{luQ5xmNUKgEEDO_c5LoJCum}

Romeo and Juliet

Neobeo
5 solves / 495 points
Romeo and Juliet have opened a secure channel where they can feel free to say anything they want to each other.

nc win.the.seetf.sg 3001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import getPrime, bytes_to_long
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

class Person:
    def __init__(self):
        p, q = getPrime(512), getPrime(512)
        self.e = 65537
        self.d = pow(self.e, -1, (p-1)*(q-1))
        self.n = p * q
    def hear(self, m): return pow(m, self.e, self.n)
    def yell(self, c): return pow(c, self.d, self.n)
        
Romeo, Juliet = Person(), Person()

noise = os.urandom(16)
print('Romeo hears the flag amidst some noise:', Romeo.hear(bytes_to_long(noise[:8] + flag + noise[8:])))

for _ in noise:
    print('Juliet hears:', Juliet.hear(Romeo.yell(int(input('Romeo yells: ')))))
    print('Romeo hears:', Romeo.hear(Juliet.yell(int(input('Juliet yells: ')))))

题目逻辑很简单，简而言之就是我们拥有使用 Romeo 的RSA公钥加密的 flag 的密文 $m^e \equiv c \pmod {n_r}$，然后题目提供了十六次的交互机会，每一次交互分为两部分，第一部分会用 Romeo 的私钥解密再用 Juliet 的公钥加密输出；第二部分会用 Juliet 的私钥解密再用 Romeo 的公钥加密（等价于 Romeo 和 Juliet 在使用 RSA 进行加密通信，而我们则是一个中间人的角色）

我们设 Romeo 的公私钥对为 $(e,n_r),(d_r)$ ， Juliet 的公私钥对为 $(e,n_j),(d_j)$ 。那么想要解密 flag，至少是需要先拿到双方的公钥，假设 $n_r < n_j$，我们在第一次交互的第一部分传入 -1，那么就有 $ouput \equiv (-1^{d_r} \pmod {n_r})^e \pmod{n_j} \equiv (n_r -1) \pmod {n_j} = n_r -1$

有了 $n_r$，我们可以计算数据 $2^e \pmod {n_r}$ ，用于第二部分的交互得到 $output\equiv (2^{ed_r} \pmod {n_r})^e \pmod {n_j} \equiv 2^e \pmod {n_j}$，于是我们有 $2^e-output = k_2n_j$，如此我们可以还可以得到 $k_3n_j,k_4n_j$，然后求一个 GCD 就可以得到 $n_j$ 了。

那么该怎么解 flag 呢？我们拥有 $m^e \equiv c \pmod {n_r}$，如果在一次交互中我们第一次把这个 $c$ 传过去，我们能够得到 $(c^{d_r} \pmod {n_r})^e \pmod {n_j} \to m^e \pmod {n_j}$

如果我们传入 $-c$，则会得到 $(((-c)^{d_r} \pmod {n_r})^e \pmod {n_j} \to (-m \pmod {n_r})^e \pmod {n_j} \to (n_r-m)^e \pmod {n_j}$

这样我们拥有两条相关明文的密文了，尝试一下 franklinReiter 明文相关攻击，发现由于 $e$ 太大了，运行内存会炸RecursionError: maximum recursion depth exceeded while calling a Python object。github上有一个 crypto-attacks 项目，里面有一个 fast_polynomial_gcd，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import logging
from pwn import *
from functools import reduce
from Crypto.Util.number import *


# context.log_level = 'debug'
# sh = remote('win.the.seetf.sg', 3001)
sh = process(["python3", "romeo_and_juliet.py"])


def _polynomial_hgcd(ring, a0, a1):
    assert a1.degree() < a0.degree()

    if a1.degree() <= a0.degree() / 2:
        return 1, 0, 0, 1

    m = a0.degree() // 2
    b0 = ring(a0.list()[m:])
    b1 = ring(a1.list()[m:])
    R00, R01, R10, R11 = _polynomial_hgcd(ring, b0, b1)
    d = R00 * a0 + R01 * a1
    e = R10 * a0 + R11 * a1
    if e.degree() < m:
        return R00, R01, R10, R11

    q, f = d.quo_rem(e)
    g0 = ring(e.list()[m // 2:])
    g1 = ring(f.list()[m // 2:])
    S00, S01, S10, S11 = _polynomial_hgcd(ring, g0, g1)
    return S01 * R00 + (S00 - q * S01) * R10, S01 * R01 + (S00 - q * S01) * R11, S11 * R00 + (S10 - q * S11) * R10, S11 * R01 + (S10 - q * S11) * R11


def fast_polynomial_gcd(a0, a1):
    """
    Uses a divide-and-conquer algorithm (HGCD) to compute the polynomial gcd.
    More information: Aho A. et al., "The Design and Analysis of Computer Algorithms" (Section 8.9)
    :param a0: the first polynomial
    :param a1: the second polynomial
    :return: the polynomial gcd
    """
    # TODO: implement extended variant of half GCD?
    assert a0.parent() == a1.parent()

    if a0.degree() == a1.degree():
        if a1 == 0:
            return a0
        a0, a1 = a1, a0 % a1
    elif a0.degree() < a1.degree():
        a0, a1 = a1, a0

    assert a0.degree() > a1.degree()
    ring = a0.parent()

    # Optimize recursive tail call.
    while True:
        logging.debug(f"deg(a0) = {a0.degree()}, deg(a1) = {a1.degree()}")
        _, r = a0.quo_rem(a1)
        if r == 0:
            return a1.monic()

        R00, R01, R10, R11 = _polynomial_hgcd(ring, a0, a1)
        b0 = R00 * a0 + R01 * a1
        b1 = R10 * a0 + R11 * a1
        if b1 == 0:
            return b0.monic()

        _, r = b0.quo_rem(b1)
        if r == 0:
            return b1.monic()

        a0 = b1
        a1 = r
        

sh.recvuntil(b"noise: ")
c = int(sh.recvuntil("\n")[:-1])


def oracle1(c):
    # pow(pow(c, d1, n1), e2, n2)
    sh.recvuntil(b"Romeo yells: ")
    sh.sendline(str(c))
    sh.recvuntil(b"Juliet hears: ")
    return int(sh.recvuntil("\n")[:-1])


def oracle2(c):
    # pow(pow(c, d2, n2), e1, n1)
    sh.recvuntil(b"Juliet yells: ")
    sh.sendline(str(c))
    sh.recvuntil(b"Romeo hears: ")
    return int(sh.recvuntil("\n")[:-1])


e = 65537

n1 = oracle2(oracle1(-1)) + 1

n2_2 = oracle1(pow(2, e, n1)) - 2**e
oracle2(0)
n2_3 = oracle1(pow(3, e, n1)) - 3**e
oracle2(0)
n2_5 = oracle1(pow(5, e, n1)) - 5**e
oracle2(0)

n2 = reduce(GCD,[n2_2,n2_3,n2_5])

assert n1<n2,"try again"

c1 = oracle1(c)
oracle2(0)
c2 = oracle1(-c)

P.<x> = Zmod(n2)[]
f1 = x^e-c1
f2 = (n1-x)^e-c2
h = fast_polynomial_gcd(f1,f2)
m = long_to_bytes(int(-h[0]))
print(m)

Isogeny Maze

Neobeo
4 solves / 496 points
We had a maze last year called To Infinity. Here’s the sequel.

nc win.the.seetf.sg 3000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import os
flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}')

p = 2^8 * 3^15 - 1
F.<i> = GF(p^2, modulus=x^2+1)
j = F(0)

print('''\
 _____                                    __  __      
|_   _|                                  |  \/  |              
  | |  ___  ___   __ _  ___ _ __  _   _  | \  / | __ _ _______ 
  | | / __|/ _ \ / _` |/ _ \ '_ \| | | | | |\/| |/ _` |_  / _ \\
 _| |_\__ \ (_) | (_| |  __/ | | | |_| | | |  | | (_| |/ /  __/
|_____|___/\___/ \__, |\___|_| |_|\__, | |_|  |_|\__,_/___\___|
                  __/ |            __/ |                       
                 |___/            |___/
Welcome to the Isogeny Maze! Substrings of pi contain the flag.''')

for _ in range(100):
    E = EllipticCurve(j = j)
    print('-'*63)
    print(f'You are in Town {j}.')
    if str(j) in '31415926535897932384626433832795':
        print(f'There is a flag in this town: {flag}')
    
    neighbours = [E.isogeny_codomain(m).j_invariant() for m in E(0).division_points(2)]
    neighbours = sorted(set(neighbours) - {j})
    roadmsg = 'is only 1 road' if len(neighbours) == 1 else f'are {len(neighbours)} roads'
    print(f'There {roadmsg} out of here:')
    for i,n in enumerate(neighbours):
        print(f'* Road [{i+1}] leads to Town {n}')
    print('Which road would you like to take?')
    try:
        j = neighbours[int(input())-1]
    except (ValueError, IndexError):
        print('Invalid road.')
        pass

代码不长，但全是知识盲区。首先题目定义了一个不大的 $p$ 和一个虚数域。然后初始化了一个 $j=0$，和一个曲线 E = EllipticCurve(j = j) （第一次见这样定义曲线的），接着题目选取了曲线的零点 E(0)，并将其进行 “除 2” 的操作（等价于找到阶为2的点）。由于定义在虚数域，有四个解（四个解的 j_invariant 可能有重复），其中两个是实数解，两个是虚数解。接着由选手选定一个 j_invariant，题目以选手的选择为 核(kernel) 将当前曲线映射 $E$ 到另一条同源的曲线 $E’$，再对该曲线 $E’$ 的零点进行 “除2” 操作。不断循环这样的交互，最多100 次，当选手选定曲线的 j_invariant 是 ‘31415926535897932384626433832795’ 的子串时获得 flag。

整个逻辑可以画成图：

我们需要找到一条长度小于 100 的能够让 j_invariant 满足条件的路径。

这里完全依照 maple 的思路进行的复现。首先由于曲线同源，所以映射后的曲线仍然时超奇异曲线，因此我们可以先将目标 j_invariant 确定下来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random

p = 2 ^ 8 * 3 ^ 15 - 1
F.<i> = GF(p^2, modulus=x^2+1)
Estart = EllipticCurve(j=F(0))
Eend = EllipticCurve(j=F(314159))


while True:
    pis = "31415926535897932384626433832795"
    st = random.randrange(0, len(pis) - 1)
    ed = random.randint(st + 1, len(pis))
    jj = F(int(pis[st:ed]))
    if EllipticCurve(j=jj).is_supersingular():
        print(jj)
        break

多次运行发现只有当 $j=314159$ 时才满足条件，于是问题就变成如何选择路径使得 $j:0\to 314159$。

这里理论上在本地我们也可以用递归的算法，比如 BFS,DFS 搜一下；然后为了加速可以尝试 MITM 算法，不过知识盲区，并不知道怎么从终点逆映射回来。maple也找到了一个 implementation，能够快速的找到路径，本质是不再通过 sage 自带的 isogeny_codomain 去计算新的曲线的 j_invariant ，而是根据解一个 $\Phi$ 函数（一元三次方程）来计算j_invariant 的相邻值，然后附上 DFS 和 MITM 就能够快速的找到路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
from sage.all import GF, var, PolynomialRing
from collections import deque

x = var("x")
p = 2**8 * 3**15 - 1
Fp2 = GF(p**2, "i", modulus=x**2 + 1)

Fp2_inv_2 = Fp2(1) / 2


def sqrt_Fp2(a):
    p = Fp2.characteristic()
    i = Fp2.gens()[0]  # i = √-1

    a1 = a ** ((p - 3) // 4)
    x0 = a1 * a
    α = a1 * x0

    if α == -1:
        x = i * x0
    else:
        b = (1 + α) ** ((p - 1) // 2)
        x = b * x0

    return x


def quadratic_roots(b, c):
    d2 = b**2 - 4 * c
    d = sqrt_Fp2(d2)
    return ((-b + d) * Fp2_inv_2, -(b + d) * Fp2_inv_2)


def generic_modular_polynomial_roots(j1):
    R = PolynomialRing(j1.parent(), "y")
    y = R.gens()[0]
    Φ2 = (
        j1**3
        - j1**2 * y**2
        + 1488 * j1**2 * y
        - 162000 * j1**2
        + 1488 * j1 * y**2
        + 40773375 * j1 * y
        + 8748000000 * j1
        + y**3
        - 162000 * y**2
        + 8748000000 * y
        - 157464000000000
    )

    return Φ2.roots(multiplicities=False)


def quadratic_modular_polynomial_roots(jc, jp):
    jc_sqr = jc**2
    α = -jc_sqr + 1488 * jc + jp - 162000
    β = (
        jp**2
        - jc_sqr * jp
        + 1488 * (jc_sqr + jc * jp)
        + 40773375 * jc
        - 162000 * jp
        + 8748000000
    )
    # Find roots to x^2 + αx + β
    return quadratic_roots(α, β)


def find_j_invs(j1, l, j_prev=None):
    if l != 2:
        raise ValueError("Currently, `find_j_invs` is only implemented for l=2")

    if j_prev:
        roots = quadratic_modular_polynomial_roots(j1, j_prev)

    else:
        roots = generic_modular_polynomial_roots(j1)

    # Dont include the the previous node to avoid backtracking
    return [j for j in roots if j != j_prev]


def find_isogeny(start, end, l=2, max_depth=15):
    stk = []
    stk.append((Fp2(start), 0))  # (j, depth)
    parent = {}
    parent[start] = None
    while len(stk) > 0:
        j, depth = stk.pop()
        if depth >= max_depth:
            continue
        for jn in find_j_invs(j, 2, parent[j]):
            if jn not in parent:
                parent[jn] = j
                stk.append((jn, depth + 1))

    stk = []
    stk.append((Fp2(end), 0))  # (j, depth)
    parent2 = {}
    parent2[end] = None
    while len(stk) > 0:
        j, depth = stk.pop()
        if depth >= max_depth:
            continue
        for jn in find_j_invs(j, 2, parent2[j]):
            if jn not in parent2:
                parent2[jn] = j
                stk.append((jn, depth + 1))
            if jn in parent:
                ret = []
                t = jn
                ret.append(t)
                while (t := parent[t]) is not None:
                    ret.append(t)
                ret.reverse()
                t = jn
                while (t := parent2[t]) is not None:
                    ret.append(t)
                return ret


for j in find_isogeny(0, 314159):
    print(j)

Shard

Neobeo
1 solve / 499 points
I overheard Alice sharing a flag with Bob, but it was encrypted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secrets import randbelow
from hashlib import sha256
from math import isqrt
import os

flag = os.environ.get('FLAG', 'SEE{not_the_real_flag}').encode()

p, q = getPrime(512), getPrime(512)
n = (p * q)**3
a = randbelow(3**1337); A = pow(3, a, n)
b = randbelow(3**1337); B = pow(3, b, n)
shared = pow(A, b, n)
assert shared == pow(B, a, n)

key = sha256(str(shared).encode()).digest()
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()
hint = isqrt(p) ^ isqrt(q)

print(f'{n=}')
print(f'{A=}')
print(f'{B=}')
print(f'{ct=}')
print(f'{hint=}')

# Code ends here. The output is printed below.
'''
n=
A=
B=
ct='fc8c67c8c451db0277fdc0b3ee6cd8e4d6584e00079a3326413450a1e816f4b463fa6e58148e25145cbdd0703847bc48'
hint=27232338411805533611504752479750933666365962695083952636081656664814520651947
'''

又是很短的题面，题目使用 DH 的协商密钥的sha256 作为 AES-Key 加密了 flag， AES-Key = $A^b \equiv B^a \pmod {(p\cdot q)^3}$，我们需要解决 DHP，目前想要解决 DHP 则需要解一个 DLP，而在解 DLP 之前呢，我们需要先把 $n=(p\cdot q)^3$ 给分解了，题目额外给出了 $hint = \lfloor \sqrt p \rfloor \oplus \lfloor\sqrt q \rfloor$，这里就是我们分解 $n$ 的切入点了。

由于取整的原因，我们会有 $p-(\lfloor \sqrt p \rfloor)^2 \le 2^{256}$

设 $n’ = \sqrt[3]{n}$，那么根据上述不等式（和已知 $p,q$ 的 msb 的比特位数 $i$）的关系（外加本地测试发现）有
$$
0 \le n’- (\lfloor \sqrt p \rfloor)^2 \cdot (\lfloor\sqrt q \rfloor)^2 \le 2^{1024+1-i}
$$

$$
0 \le \sqrt {n’} - \lfloor \sqrt p \rfloor \cdot \lfloor\sqrt q \rfloor \le 2^{512-i}
$$

于是我们开始逐比特爆破 $\lfloor \sqrt{p} \rfloor$ 和，（脚本仍然来自 mapple）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from binteger import Bin
from gmpy2 import iroot

n=1161015060421173249378489750696141214060303995923395409949869627290702414711037093526198110777404654144671511905235970901959421941338918435310121680847960495861908297742489794351582662630349642895448557106366299469185588064602696326307097833183222618147069201840931225638628664922527925446087898861911362296363707119536526988582293048832383727953537307881230552636876712648271763176414090693303330350561279137776236795557842517619318238674985177929118712632535276039722205485150858981762083451832198822805690978929644453571222056709020149454001970560788598661970600271777421115525813743829030780059906217282681595452585004568419042410526300322447735538760602735954395278435630672731534059367618977970735807007280799837797901568012970516722520855615007870137859951477843419061096544616574048523021228941390127574301951810764886209442755752935524998421986069973124626502475162497047801043794416002937577783146899612599092388787
A=876856141867292541860323607264082069255499862749334652735605729433263443804539762724150146934351375350393080114923847779749893293139584686005392355141769986430382993358683972707818914126482354483753880940178023315634960922958253129075068286464920817560904484085316514309721680971508734869398801188634461566010739991385436551918949592308754421274535616460564680136888906568520377323715782357509089190820453332054156572172466552802449761288220780274972832498692580255837884665986978378035841349843031182334647618147782842049846153066181892449539407745486014499636387858777511312613142984882310305184710764200146570459723866686802492176613030166678729173421755638026624369502464133911152877741923335829863164896950580382969467402969579748979746430740394953571425965962087121649198611419063708096301382847206823372253864792103755888994838934565521982402277844450137390594607102522657031671082063652219166034186562490760814532579
B=287632227917624654212614562649343874383417428057330805237209169637026908557410569116739444108514384266685475678850601667911684150076525797991252031688869217089950247006850937786118259851817500044754131047963987707992467875713170336353659270924179467464836139578541900688370920519460119004845929450828524305499363274758459994420143563155593544731412056092492994042903315707705208959629847419957728142635524372296868834143016326096908127353866551528921319266146109788458033229140227479625927790051152685157231719361353398932500869549791514313894503151218196435978062246049426212499132086244127866741759522252412600587230711377821184153990120408229678096104763349842116878130234588134513252819344719559051734230776027339643260314327324982833200026332745447375624996928647322777183407239934048172826864244183355762705665502558087550433846102991894817404579682993484842986669591555105822532717319110007844731813526601115030730216
ct='fc8c67c8c451db0277fdc0b3ee6cd8e4d6584e00079a3326413450a1e816f4b463fa6e58148e25145cbdd0703847bc48'
hint=27232338411805533611504752479750933666365962695083952636081656664814520651947
pq = iroot(n, 3)[0]

def dfs(spv, i):
    if i >= 256:
        yield Bin(spv, 256), Bin(Bin(spv).int ^^ hint, 256)
    if i >= 256:
        return
    for b in (1, 0):
        spv[i] = b
        tsp = Bin(spv).int
        tsq = tsp ^^ hint
        p = tsp**2
        q = tsq**2
        if 0 <= (pq - p * q) <= 2 ** (1024 - i + 1) and 0 <= (
            isqrt(pq) - tsp * tsq
        ) <= 2 ** (512 - i):
            yield from dfs(spv[:], i + 1)


spv = [0] * 256
results = []
for spc, sqc in dfs(spv, 0):
    results.append(spc)

于是我们得到 9 个候选值，假设已知 $$\lfloor \sqrt{p} \rfloor$$，我们计算 $\lfloor \sqrt{p} \rfloor^2$ 后还缺低 256 位，根据 copper 的界，256 有点极限，所以我们采取爆破几位以换取 copper 的效率。

使用 sagemath 自带的 LLL 算法还是太慢了，这里使用 flatter ，（但量太大了，仍然要很长的时间，，，，）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import time
from subprocess import check_output
from re import findall

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

def small_roots(self, X=None, beta=1.0, epsilon=None, **kwds):
    from sage.misc.verbose import verbose
    from sage.matrix.constructor import Matrix
    from sage.rings.real_mpfr import RR

    N = self.parent().characteristic()

    if not self.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    beta = RR(beta)
    if beta <= 0.0 or beta > 1.0:
        raise ValueError("0.0 < beta <= 1.0 not satisfied.")

    f = self.change_ring(ZZ)

    P, (x,) = f.parent().objgens()

    delta = f.degree()

    if epsilon is None:
        epsilon = beta / 8
    verbose("epsilon = %f" % epsilon, level=2)

    m = max(beta**2 / (delta * epsilon), 7 * beta / delta).ceil()
    verbose("m = %d" % m, level=2)

    t = int((delta * m * (1 / beta - 1)).floor())
    verbose("t = %d" % t, level=2)

    if X is None:
        X = (0.5 * N ** (beta**2 / delta - epsilon)).ceil()
    verbose("X = %s" % X, level=2)

    # we could do this much faster, but this is a cheap step
    # compared to LLL
    g = [x**j * N ** (m - i) * f**i for i in range(m) for j in range(delta)]
    g.extend([x**i * f**m for i in range(t)])  # h

    B = Matrix(ZZ, len(g), delta * m + max(delta, t))
    for i in range(B.nrows()):
        for j in range(g[i].degree() + 1):
            B[i, j] = g[i][j] * X**j

    B = flatter(B)

    f = sum([ZZ(B[0, i] // X**i) * x**i for i in range(B.ncols())])
    R = f.roots()

    ZmodN = self.base_ring()
    roots = set([ZmodN(r) for r, m in R if abs(r) <= X])
    Nbeta = N**beta
    return [root for root in roots if N.gcd(ZZ(self(root))) >= Nbeta]
    
def copp_factor(sp, leak=6):
    for tb in range(1 << leak):
        print("copp", tb, int(time.time()))
        shift = 256 - leak
        P = Zmod(pq)["x"]
        x = P.gen()
        f = sp.int**2 + (tb << shift) + x
        X = 2 ** (256 - leak)
        beta = 0.499
        eps = 0.01
        # rs = f.small_roots(X=X, beta=beta, epsilon=eps)
        rs = small_roots(f, X=X, beta=beta, epsilon=eps)
        if len(rs):
            return sp.int**2 + (tb << shift) + int(rs[0])


for spci in results:
    print(spci)
    print(i, p := copp_factor(Bin(spci, 256)))
    if p:
        q = pq // p
        print(p, q)
        assert p * q == pq
        break

解出得到 $p,q$ 后还需要解决 DHP，由于这里的 $A$ 是在模 $(p\cdot q)^3$，需要先在子群 $p^3$ 和 $q^3$ 下解出再CRT。不过由于这里 $p-1$ 并不是一个光滑数，所以这里的 DLP 无法解决。但是可以用 p-adic 算法解出 $x \pmod {p^2}$，

1
2
3
4
5
6
7
8
9
10
11
p = 8129350453106964681981850657424361197868719068307155378517865139012909625358514986412144556443475408498368894473527345313464525210359939656469319473379609
q = 12928756962141621663737182425248055214929395219540084782749763068857850434179513938210598665313261500420230870895626152031543945517367275541087607313553987

Rp = Zp(p, 3)
a_mod_p2 = (Rp(A).log()/Rp(3).log()).lift()

# 30402963509775040277797093608969200119572697578159200995371352133313833520551135929586351720741987047419932380061898524835616690299065196931412079768716049483178684083946651863252863901276487663333092747098461913783063590198093489545427793369262251094895386893047537653523079132523684567903626738878952323491

Rq = Zq(q, 3)
a_mod_q2 = (Rq(A).log()/Rq(3).log()).lift()
# 158752366209466757513383261284222809866382031678797794781217717750148666579229218558365883582022038256648587390913172400122499561709522311576299296421653163130834865162164516954575735020538583592770301733468350488975139006187409012114514797173066498123352839099275308360064365264702360141107327620297454148894

这里计算一下大小，a 大约为2120比特，$p^2q^2$ 大约有 2048 比特。我们只需要再在子群 $p,q$ 下找到大约 72 比特就足够了。

看一下 p-1,q-1的小因子，把其中的大因子剔除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bigfactor_p = 1959820416307046535223558836872409986635598251161899159264123569744487202217621311192551314468443514345911835240205470995427509406607734841
bigfactor_q = 29959119000199690269712965540702271390974156502261317099624887976435590583657556550911711352412637519078021289573136033385314147803936469913672429

ordp = (p-1)//bigfactor_p
ordq = (q-1)//bigfactor_q

R = Zmod(p**3)
a_mod_ordp = discrete_log_lambda(R(A) ** (p**2 * bigfactor_p), R(3) ** (p**2 * bigfactor_p), bounds=(0,ordp))
# 78605252

R = Zmod(q**3)
a_mod_ordq = discrete_log_lambda(R(A) ** (q**2 * bigfactor_q), R(3) ** (q**2 * bigfactor_q), bounds=(0,ordq))

# 3733974878864074

最后再一起来一个 CRT 就行了。

1
2
3
4
5
6
7
8
9
10
from Crypto.Cipher import AES
from hashlib import sha256
from Crypto.Util.Padding import unpad

a = crt([a_mod_p2, a_mod_q2, a_mod_ordp, a_mod_ordq], [p**2, q**2, ordp, ordq])
shared = pow(B, a, n)
key = sha256(str(shared).encode()).digest()
flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(bytes.fromhex(ct)), 16)
print(flag)
# SEE{Cryptic_clue:_Bit_of_RSA_mixed_with_DH}

总体来看题目的思路并不难，但是每一步的界都卡的挺死的，想要在有限的时间内做出来就需要优化，算是老知识里学到许多新姿势。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com

赏

文章标题:2023 SEECTF

文章字数:8.9k

本文作者:Van1sh

发布时间:2023-06-15, 10:55:00

最后更新:2023-08-14, 20:38:53

原始链接:http://jayxv.github.io/2023/06/15/2023 seectf/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2020 Van1sh

Built with Hexo and 3-hexo theme

目录
×

喜欢就点赞,疼爱就打赏